package Top_Interview_Questions.Greedy;

/**
 * @Author: 吕庆龙
 * @Date: 2020/1/21 17:21
 * <p>
 * 功能描述:
 */
public class _0044 {
    public static void main(String[] args) {
        _0044 test = new _0044();
        String s = "acdcb";
        String p = "a*c?b";
        test.isMatch1(s,p);
    }


/*---------------------------------------双指针法---------------------------------------*/

    /**
     * 双指针法还没看
     */
    public boolean isMatch2(String s, String p) {
        int sn = s.length();
        int pn = p.length();
        int i = 0;
        int j = 0;
        int start = -1;
        int match = 0;

        while (i < sn)
        {
            //一对一匹配,匹配成功一起移
            if (j < pn && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?'))
            {
                i++;
                j++;
            }
            //记录p的"*"的位置,还有s的位置
            else if (j < pn && p.charAt(j) == '*')
            {
                start = j;
                match = i;
                j++;
            }
            //j 回到 记录的下一个位置
            //match 更新下一个位置
            //这不代表用*匹配一个字符
            else if (start != -1)
            {
                j = start + 1;
                i = ++match; //等价于先match++ ,然后i=match
            }
            else
            {
                return false;
            }
        }
        //将多余的 * 直接匹配空串
        while (j < pn)
        {
            if (p.charAt(j) != '*')
                return false;
            j++;
        }
        return true;
    }


/*---------------------------------------动态规划---------------------------------------*/

    /**
     * ①https://leetcode-cn.com/problems/wildcard-matching/solution
     * /shuang-zhi-zhen-he-dong-tai-gui-hua-by-powcai/
     *
     * ②https://leetcode-cn.com/problems/wildcard-matching/solution
     * /dong-tai-gui-hua-si-yao-su-by-a380922457-4/
     * 上面两篇解释结合起来看
     *
     *
     * 1.dp[i][j-1],表示*代表是空字符,例如ab,ab*
     * dp[i-1][j],表示*代表非空任何字符,例如abcd,ab*
     * 2.为什么初始化,以及为什么这样初始化,第②篇评论里有
     * 3.dp[i][j] = dp[i - 1][j - 1];我如果要知道s1的前i个字符，和s2的前j个字符，能否匹配？
     * 那么我只需要知道s1的前i-1个字符和j-1个字符是否匹配。因为它第i个字符和第j个字符已经匹配了。
     * -->if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?')
     *
     * #.还有一个问题,注意为什么除了dp[0][0]是true,dp[i][0]全都是false
     * #.此题动态规划理解的还不够透彻
     */
    public boolean isMatch1(String s, String p) {
        boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
        dp[0][0] = true;
        //2.
        for (int j = 1; j < p.length() + 1; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[0][j] = dp[0][j - 1];
            }
        }
        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 1; j < p.length() + 1; j++) {
                if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
                    //3.
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    //1.
                    dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
                }
            }
        }
        return dp[s.length()][p.length()];

    }

}
